package com.klun.likou;


import com.klun.Utils.GenUtil;

import javax.swing.tree.TreeNode;

public class Solution2 {

	public static void main(String[] args) {
		// 生成随机不重复数组
		int[] prices = GenUtil.genIntArrDiff(9000, 1, 20000);
		for (Integer price : prices) {
			System.out.print(price + ",");
		}
		System.out.println();
		long l = System.currentTimeMillis();
		int i = maxProfit(prices);
		long ll = System.currentTimeMillis();
		System.out.println(ll - l);
		int j = maxProfitG(prices);
		long lll = System.currentTimeMillis();
		System.out.println(lll - ll);
		System.out.println();
	}

	/**
	 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
	 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
	 * 注意你不能在买入股票前卖出股票。
	 *
	 * @param prices
	 * @return
	 */
	public static int maxProfit(int[] prices) {
		// 计算最大利润
		return digui(0, prices.length, prices);
	}

	private static int digui(int start, int end, int[] prices) {
		if (end <= start + 1) return 0;
		if (null == prices) return 0;
		int min = start, max = start;
		// 冒泡找到max
		int maxVal = prices[start];
		for (int i = start + 1; i < end; i++) {
			if (prices[i] >= maxVal) {
				max = i;
				maxVal = prices[i];
			}
		}
		if (max == 0) return digui(start + 1, end, prices);
		int minVal = prices[start];
		for (int i = start + 1; i < max; i++) {
			if (prices[i] <= minVal) {
				min = i;
				minVal = prices[i];
			}
		}
		return Math.max(prices[max] - prices[min], digui(max + 1, end, prices));
	}

	/**
	 * 官方题解
	 *
	 * @param prices
	 * @return
	 */
	public static int maxProfitG(int prices[]) {
		int minprice = Integer.MAX_VALUE;
		int maxprofit = 0;
		for (int i = 0; i < prices.length; i++) {
			if (prices[i] < minprice)
				minprice = prices[i];
			else if (prices[i] - minprice > maxprofit)
				maxprofit = prices[i] - minprice;
		}
		return maxprofit;
	}
}
